package oct2013;

import java.util.ArrayList;
import java.util.HashMap;

public class SubstringwithConcatenationofAllWords {
	public ArrayList<Integer> findSubstring(String S, String[] L) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		int len = S.length();
		int n = L.length;
		int k = L[0].length();
		HashMap<String, Integer> dict = new HashMap<String, Integer>();
		for (int i = 0; i < n; ++i) {
			Integer val = dict.get(L[i]);
			if (val == null) {
				val = 0;
			}
			dict.put(L[i], val + 1);
		}
		HashMap<String, Integer> obtain = new HashMap<String, Integer>();
		for (String key : dict.keySet()) {
			obtain.put(key, 0);
		}
		for (int i = 0; i < k; ++i) {
			clear(obtain);
			int cnt = 0;
			int left = i;
			for (int j = i; j < len; j += k) {
				if (j + k > len)
					break;
				String str = S.substring(j, j + k);
				if (!dict.containsKey(str)) {
					while (!S.substring(left, left + k).equals(str)) {
						decrease(obtain, S.substring(left, left + k));
						left += k;
						cnt--;
					}
					left = j + k;
					cnt = 0;
				} else {
					if (obtain.get(str).intValue() == dict.get(str).intValue()) {
						while (!S.substring(left, left + k).equals(str)) {
							decrease(obtain, S.substring(left, left + k));
							left += k;
							cnt--;
						}
						decrease(obtain, S.substring(left, left + k));
						left += k;
						cnt--;
					}
					increase(obtain, str);
					cnt++;
					if (cnt == n)
						res.add(left);
				}
			}
		}
		return res;
	}

	void clear(HashMap<String, Integer> obtain) {
		for (String key : obtain.keySet()) {
			obtain.put(key, 0);
		}
	}

	void increase(HashMap<String, Integer> obtain, String key) {
		obtain.put(key, obtain.get(key) + 1);
	}

	void decrease(HashMap<String, Integer> obtain, String key) {
		obtain.put(key, obtain.get(key) - 1);
	}

	public static void main(String[] args) {
		SubstringwithConcatenationofAllWords a = new SubstringwithConcatenationofAllWords();
		a.findSubstring("barfoothefoobarman", new String[] { "foo", "bar" });
	}
}
